package maxHeap2;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/18 14:38
 * 添加replace和heapify
 */
public class MaxHeap<E extends Comparable<E>> {


    private DynamicArrayT<E> data;

    public MaxHeap(int capacity) {
        this.data = new DynamicArrayT<>(capacity);
    }

    public MaxHeap() {
        data = new DynamicArrayT<>();
    }

    public MaxHeap(E[] arr){
        data = new DynamicArrayT<>(arr);

        for (int i = parent(arr.length-1); i >=0; i--) {
            siftDown(i);
        }
    }


    public int size(){
        return data.getSize();
    }


    public boolean isEmpty(){
        return data.isEmpty();
    }
    //返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index==0){
            throw  new IllegalArgumentException("index-0 没有父节点");
        }
        return (index - 1)/2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }

    //向堆中添加元素
    public void add(E e){
        data.addLast(e);
        //添加元素到末尾，然后上浮
        siftUp(data.getSize()-1);
    }
    //    最大堆添加的上浮操作
    private void siftUp(int k) {
        while (k > 0 && data.getElementByIndex(parent(k))
                .compareTo( data.getElementByIndex(k) ) < 0){
            //父亲元素比较小--交换
                data.exchange(k,parent(k));
                k=parent(k);
        }
    }




    //查看出堆中的最大元素
    public E findMax(){
        if(data.getSize()==0){
            throw new IllegalArgumentException("堆是空的，不能获取最大值");
        }
        return  data.getElementByIndex(0);
    }


    //取出堆中的最大值
    public E extractMax(){
        E ret = findMax();
        data.exchange(0,data.getSize()-1);
        data.removeLast();
        //下沉操作
        siftDown(0);

        return ret;
    }

    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()){
            int j = leftChild(k);
            //有右孩子并且右孩子比左孩子大
            if(j+1 < data.getSize() &&
            data.getElementByIndex(j+1).compareTo(data.getElementByIndex(j)) > 0){
//                j++;
                j=rightChild(k);
            }

            //data[j]是leftChild和rightChild中的最大值
            //如果k结点的值比 最大的孩子结点还要大，那就不需要下沉了，直接退出循环
            if(data.getElementByIndex(k).compareTo(data.getElementByIndex(j))>=0){
                break;
            }

            //违反了堆的性质，需要交换 k和j[此时是孩子结点中最大值的下标] 的值
            data.exchange(k,j);
            k=j;
        }
    }


    //取出堆中的最大元素，然后替换成元素e
    public E replace(E e){
        E ret = findMax();
        data.setElement(0,e);
        siftDown(0);
        return ret;
    }


    //heatify:将任意的数组整理成堆的形状





}
